package com.barry.algorithm.search;

import java.util.*;

/**
 * 类功能描述: 二叉树遍历算法Java实现
 *
 * @version 1.0.0
 * @auther Create by Barry
 * @date Create on 2018/3/12.
 * @history
 */
public class BinaryTree {

    public List<Node> createTree(Integer[] a){
        List<Node> allNodes = new ArrayList<>();
        for(int i=0; i< a.length; i++){
            allNodes.add(new Node(a[i]));
        }

        for(int i=0; i< a.length/2-1; i++){
            allNodes.get(i).leftChild = allNodes.get(i*2+1);
            allNodes.get(i).rightChild = allNodes.get(i*2+2);
        }

        int lastIndex = a.length/2-1;
        allNodes.get(lastIndex).leftChild = allNodes.get(lastIndex*2+1);
        if(a.length%2 == 1){
            allNodes.get(lastIndex).rightChild = allNodes.get(lastIndex*2+2);
        }
        return allNodes;
    }

    /**
     * 1、 深度优先遍历
     * 1.1 递归先序遍历
     */
    public void preOrderTraverse(Node root){
        System.out.println(root.data);
        if(root.leftChild != null){
            preOrderTraverse(root.leftChild);
        }
        if(root.rightChild != null){
            preOrderTraverse(root.rightChild);
        }
    }

    /**
     * 1、 深度优先遍历
     * 1.2 实现非递归先序遍历
     */
    public void preOrder(Node root){
        Stack stack = new Stack();
        stack.push(root);
        while(!stack.isEmpty()){
            Node element = (Node)stack.pop();
            System.out.println(element.data);
            if(element.rightChild != null){
                stack.push(element.rightChild);
            }
            if(element.leftChild != null){
                stack.push(element.leftChild);
            }
        }
    }

    /**
     * 2、 广度优先遍历
     */
    public List<Node> breadthTraverse(Node root){
        List<Node> allNodes = new LinkedList<>();
        if(root == null){
            return allNodes;
        }
        Deque<Node> queue = new ArrayDeque<>();
        queue.add(root);
        while(!queue.isEmpty()){
            Node currentNode = queue.poll();
            allNodes.add(currentNode);
            if(currentNode.leftChild != null){
                queue.add(currentNode.leftChild);
            }
            if(currentNode.rightChild != null){
                queue.add(currentNode.rightChild);
            }
        }
        return allNodes;
    }

    class Node{
        private Object data;
        private Node leftChild;
        private Node rightChild;
        public Node(Object data){
            this(data, null, null);
        }

        public Node(Object data, Node leftChild, Node rightChild){
            this.data = data;
            this.leftChild = leftChild;
            this.rightChild = rightChild;
        }
    }

    public static void main(String[] args) {
        Integer[] a = new Integer[]{1, 2 , 3 ,4, 5, 6, 7};
        BinaryTree bt = new BinaryTree();
        List<Node> allNodes = bt.createTree(a);
        Node root = allNodes.get(0);
        bt.preOrderTraverse(root);
        System.out.println("=================================");
        bt.preOrder(root);
        System.out.println("=================================");
        List<Node> list = bt.breadthTraverse(root);
        for(Node node : list){
            System.out.println(node.data);
        }

    }
}
